from collections import Iterable
from collections import Mapping
from functools import reduce
from functools import total_ordering
from itertools import islice
from itertools import zip_longest
import operator

from algorithm.list import inplace_map

__all__ = ["Polynomial"]



@total_ordering
class Polynomial:

    __slots__ = ("_coeff",)

    def __init__(self, other = None):
        klass = type(self)
        member_type = klass.member_type
        if not other:
            self._coeff = []
        elif type(other) == klass:
            self._coeff = other._coeff[:]
        elif isinstance(other, Polynomial):
            self._coeff = [member_type(x) for x in other._coeff]
            self.remove_leading_zeros()
        elif isinstance(other, Iterable):
            self._coeff = [member_type(x) for x in other]
            self.remove_leading_zeros()
        else:
            self._coeff = [member_type(other)]
            self.remove_leading_zeros()

    def init(self, iterable):
        member_type = type(self).member_type
        if isinstance(iterable, Mapping):
            for deg, coeff in iterable.items():
                self[deg] = coeff
        else:
            self._coeff = [member_type(x) for x in iterable]
            self.remove_leading_zeros()

    def assign(self, mapping):
        for deg, coeff in mapping.items():
            self[deg] = coeff

    def __eq__(self, other):
        return self._coeff == other._coeff

    def __lt__(self, other):
        l1 = len(self._coeff)
        l2 = len(other._coeff)
        if l1 < l2:
            return True
        elif l1 > l2:
            return False
        for x, y in zip(reversed(self._coeff), reversed(other._coeff)):
            if x < y:
                return True
            elif x > y:
                return False
        return False

    def __str__(self, variable = 'x'):
        one = type(self).one
        l = []
        for deg, coeff in filter(lambda x: x[1], enumerate(self._coeff)):
            if deg == 0:
                l.append(str(coeff))
            elif deg == 1:
                if coeff == one:
                    l.append(variable)
                else:
                    l.append("{0}*{1}".format(coeff, variable))
            elif coeff == one:
                l.append("{0}^{1}".format(variable, deg))
            else:
                l.append("{0}*{1}^{2}".format(coeff, variable, deg))
        s = " + ".join(reversed(l)) if l else str(type(self).zero)
        return s.replace("-1*", "-").replace("+ -", "- ")

    def __repr__(self, variable = 'x'):
        l = []
        for deg, coeff in enumerate(self._coeff):
            l.append("{0}*{1}^{2}".format(repr(coeff), variable, deg))
        return " + ".join(reversed(l)) if l else repr(type(self).zero)

    def __bool__(self):
        return bool(self._coeff)

    @property
    def deg(self):
        return len(self._coeff) - 1

    @property
    def coeff(self):
        return self._coeff

    def __getitem__(self, deg):
        if isinstance(deg, slice):
            result = type(self)()
            result._coeff = self._coeff[deg]
            return result.remove_leading_zeros()
        else:
            if deg >= len(self._coeff):
                return type(self).zero
            else:
                return self._coeff[deg]

    def __setitem__(self, deg, coeff):
        zero = type(self).zero
        coeff = type(zero)(coeff)
        length = len(self._coeff)
        if deg >= length:
            if coeff:
                self._coeff += (zero for x in range(deg - length))
                self._coeff.append(coeff)
        elif deg < length - 1 or coeff:
            self._coeff[deg] = coeff
        else:
            self._coeff[-1] = zero
            self.remove_leading_zeros()

    def remove_leading_zeros(self):
        length = len(self._coeff)
        while length > 0 and not self._coeff[length - 1]:
            length -= 1
        del self._coeff[length:]
        return self

    @property
    def leading_coeff(self):
        return self._coeff[-1] if self._coeff else type(self).zero

    def monic(self):
        if self:
            return self / self._coeff[-1]
        else:
            return type(self)()

    def to_monic(self):
        if self:
            self /= self._coeff[-1]
        return self

    def interpole(self, value):
        return reduce(lambda x, y: x * value + y,
                reversed(self._coeff), type(self).zero)

    def __lshift__(self, shift):
        other = type(self)()
        other._coeff = [type(self).zero for x in range(shift)] + self._coeff
        return other

    def __ilshift__(self, shift):
        if self._coeff:
            self._coeff[:0] = [type(self).zero for x in range(shift)]
        return self

    def __rshift__(self, shift):
        other = type(self)()
        other._coeff = self._coeff[shift:]
        return other

    def __irshift__(self, shift):
        del self._coeff[:shift]
        return self

    @classmethod
    def binary_op(klass, left, right, op):
        return klass(op(x, y) for x, y in zip_longest(
                left._coeff, right._coeff, fillvalue = klass.zero))

    def __add__(self, other):
        return self.binary_op(self, other, operator.add)

    def __iadd__(self, other):
        l1 = len(self._coeff)
        l2 = len(other._coeff)
        if l1 < l2:
            for deg in range(l1):
                self._coeff[deg] += other._coeff[deg]
            self._coeff += islice(other._coeff, l1, None)
        else:
            for deg in range(l2):
                self._coeff[deg] += other._coeff[deg]
            if l1 == l2:
                self.remove_leading_zeros()
        return self

    def __neg__(self):
        return type(self)(-x for x in self._coeff)

    def __sub__(self, other):
        return self.binary_op(self, other, operator.sub)

    def __isub__(self, other):
        l1 = len(self._coeff)
        l2 = len(other._coeff)
        if l1 < l2:
            for deg in range(l1):
                self._coeff[deg] -= other._coeff[deg]
            self._coeff += (-x for x in islice(other._coeff, l1, None))
        else:
            for deg in range(l2):
                self._coeff[deg] -= other._coeff[deg]
            if l1 == l2:
                self.remove_leading_zeros()
        return self

    def __mul__(self, other):
        klass = type(self)
        if isinstance(other, klass):
            result = klass()
            result._coeff = [klass.zero for x in
                    range(len(self._coeff) + len(other._coeff) - 1)]
            for i, x in enumerate(self._coeff):
                for j, y in enumerate(other._coeff):
                    result._coeff[i + j] += x * y
            return result.remove_leading_zeros()
        elif other:
            return klass(x * other for x in self._coeff)
        else:
            return klass()

    def __rmul__(self, other):
        if other:
            result = type(self)(x * other for x in self._coeff)
            return result.remove_leading_zeros()
        else:
            return type(self)()

    def __imul__(self, other):
        if isinstance(other, type(self)):
            self = self * other
        elif not other:
            self._coeff = []
        elif other != type(self).one:
            inplace_map(lambda x: operator.imul(x, other), self._coeff)
            self.remove_leading_zeros()
        return self

    def square(self):
        result = type(self)()
        result._coeff = [type(self).zero for x in
                range(len(self._coeff) * 2 - 1)]
        for i, x in enumerate(self._coeff):
            for j in range(i):
                result._coeff[i + j] += 2 * x * self._coeff[j]
            result._coeff[i << 1] = x ** 2
        return result.remove_leading_zeros()

    def __divmod__(self, other):
        if not other:
            raise ZeroDivisionError
        klass = type(self)
        quotient = klass()
        remainder = klass(self)
        l2 = len(other._coeff)
        deg_diff = len(remainder._coeff) - l2
        if deg_diff >= 0:
            quotient._coeff = [klass.zero for x in range(deg_diff + 1)]
            while deg_diff >= 0:
                q = remainder._coeff[-1] / other._coeff[-1]
                quotient._coeff[deg_diff] = q
                for deg, coeff in enumerate(other._coeff, deg_diff):
                    remainder._coeff[deg] -= q * coeff
                remainder.remove_leading_zeros()
                deg_diff = len(remainder._coeff) - l2
        return quotient, remainder

    def __truediv__(self, other):
        if not other:
            raise ZeroDivisionError
        return type(self)(x / other for x in self._coeff)

    def __itruediv__(self, other):
        if not other:
            raise ZeroDivisionError
        inplace_map(lambda x: operator.itruediv(x, other), self._coeff)
        return self

    def __floordiv__(self, other):
        return divmod(self, other)[0]

    def __mod__(self, other):
        if not other:
            raise ZeroDivisionError
        remainder = type(self)(self)
        remainder %= other
        return remainder

    def __imod__(self, other):
        if not other:
            raise ZeroDivisionError
        l2 = len(other._coeff)
        deg_diff = len(self._coeff) - l2
        while deg_diff >= 0:
            q = self._coeff[-1] / other._coeff[-1]
            for deg, coeff in enumerate(other._coeff, deg_diff):
                self._coeff[deg] -= q * coeff
            self.remove_leading_zeros()
            deg_diff = len(self._coeff) - l2
        return self

    def __pow__(self, exp, mod = None):
        result = type(self)(1)
        if mod is None:
            while exp:
                if exp & 1:
                    result *= self
                self = self.square()
                exp >>= 1
        else:
            while exp:
                if exp & 1:
                    result = result * self % mod
                self = self.square() % mod
                exp >>= 1
        return result

    def deriv(self):
        return type(self)(deg * self._coeff[deg]
                for deg in range(1, len(self._coeff)))
